import java.util.List;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
class Solution {
    //汉诺塔问题
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
       dfs(A, B, C, A.size());
    }

    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n){
        //递归出口
        if(n == 1){
            c.add(a.remove(a.size() - 1));
            return;   
        }
        
        dfs(a, c, b, n - 1);
        c.add(a.remove(a.size() - 1));
        dfs(b, a, c, n - 1);
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //递归出口
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        //
        if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    //反转链表
    public ListNode reverseList(ListNode head) {
        //递归出口
        if(head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }
    //两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        //递归出口
        if(head == null || head.next == null) return head;
        //交换
        ListNode next = swapPairs(head.next.next);
        ListNode newHead = head.next;
        newHead.next = head;
        head.next = next;
        //返回
        return newHead;
    }

    //快速幂
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }

    public double pow(double x, long n){
        //递归出口
        if(n == 0) return 1.0;

        double tmp = pow(x, n / 2);

        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
}